package mapreduce;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Implementation of algorithm union find
 */

public class UnionFind{
	
	// point in its string form and its parent point.
	HashMap<String, Point> map;
	
	public UnionFind() {
		map = new HashMap<String, Point>(DataToPass.DEFAULT_ELE_SIZE);
	}
	
	public void makeSet(Point x) {
		String str = x.toString();
		if(!map.containsKey(str))
			map.put(str, x);
	}
	
	/**
	 * optimized.
	 * @param p1
	 * @param p2
	 */
	public void union (Point p1, Point p2) {
		Point p1Root = find(p1);
		Point p2Root = find(p2);
		PointComparator pc = new PointComparator();
		int compare = pc.compare(p1Root, p2Root);
		if(compare > 0) {
			map.put(p1Root.toString(), p2Root);
			map.put(p1.toString(), p2Root);
		}
		else if (compare < 0) {
			map.put(p2Root.toString(), p1Root);
			map.put(p2.toString(), p1Root);
		}
	}
	
	/**
	 * optimized.
	 * @param p
	 * @return
	 */
	public Point find(Point p)
	{
		PointComparator pc = new PointComparator();
		Point newP = p;
		ArrayList<Point> points = new ArrayList<Point>();
		
		while(pc.compare(newP, map.get(newP.toString()))!=0) {
			points.add(newP);
			newP = map.get(newP.toString());
		}
		
		// optimizing
		if(points.size() > 1) {
			for (Point point : points) {
				map.put(point.toString(), newP);
			}
		}
		return newP;
	}
}

